package DMSXL._2024.BackTracking;

import java.util.ArrayList;
import java.util.List;

public class restoreIpAddresses {
    public static void main(String[] args) {
        String s =  "101023";
        System.out.println(new restoreIpAddresses().restoreIpAddresses(s));
    }
    List<String> result = new ArrayList<>();
    String temp = "";
    public List<String> restoreIpAddresses(String s) {
        backTracking(s,0,0);
        return result;
    }
    public void backTracking(String s, int startIndex , int k){
        if(startIndex == s.length() && k == 4){
            result.add(temp.substring(0,temp.length() - 1));
            return;
        }
        if(k >= 4){
            return;
        }
        for (int i = startIndex; i < startIndex + 3 && i < s.length() ; i++) {
            if(isValid(s,startIndex,i)){
                temp += s.substring(startIndex,i + 1) + ".";
            }else {
                continue;
            }
            int len = i - startIndex + 2;

            backTracking(s,i + 1, k + 1);

            temp = temp.substring(0,temp.length() -len);
        }
    }
    public boolean isValid(String s, int start, int end){
        if(end != start && s.substring(start,end + 1).charAt(0) == '0'){
            return false;
        }
        int value = Integer.parseInt(s.substring(start,end + 1));
        if(value < 0 || value > 255){
            return false;
        }
        return true;
    }
}
